package 春招冲刺百题计划;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-25
 * Time:22:30
 */

/**
 * 春招冲刺百题计划:264. 丑数 II
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * 丑数 就是质因子只包含 2、3 和 5 的正整数。
 * 示例 1：
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 */
public class nthUglyNumber {
    public static void main(String[] args) {
        nthUglyNumber(10);
    }
    public static int nthUglyNumber(int n) {
        int n2 = 0,n3 = 0,n5 = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1;i<n;i++){
            dp[i] = Math.min(2 * dp[n2],Math.min(3 * dp[n3],5 * dp[n5]));
            if(dp[i] == 2 * dp[n2]) n2++;
            if(dp[i] == 3 * dp[n3]) n3++;
            if(dp[i] == 5 * dp[n5]) n5++;
        }
        return dp[n-1];
    }
}
